1. Field of the Invention
The present invention relates to a multiprocessor system, and more particularly to such a system which provides synchronization among processes each dispatched to processors.
2. Related Art
Two key factors in parallel processing are accurate performance of data transfers among divided processes and maintenance of the execution sequence of the processes. In order to determine appropriate timing for such data transfers or the like, synchronization needs to be achieved among the processes.
Synchronization of processes is usually performed through a memory. A variable is placed in the memory, for acknowledging the establishment of synchronization. Processes to be synchronized with one another lock the bus and read/write the variable, and they consequently ascertain that synchronization has been achieved. The reason why the bus is locked is because the consistency of the variable may be destroyed if one process is allowed to read and write the variable while another process reads or writes it.
The realization of synchronization by use of a read/write of a variable in the memory is effective if the number of processes to be synchronized is small and if the frequency of synchronization is small. However if the number of processes to be synchronized is large and the synchronization is frequently performed, realization of synchronization through a memory is inefficient.
Since only one processor can hold the bus to make reference to the memory at a time, the synchronization through the memory causes serialization of processes. In addition, the more frequently the bus is locked, the more the other processing is affected, which results worse performance of the multiprocessor system as a whole. Further when an instruction sequence between consecutive synchronizations includes only a few steps, the ratio of overhead by instructions required to provide the above synchronization over total overhead increases.
Accordingly, in an application where parallelism is much exploited and frequent synchronization is needed, synchronization among processes assigned to processors needs to be performed at a high speed by a technique that does not use a memory and a shared common bus. Several techniques have been previously proposed.
For example, there is available a technique for lessening the frequency of access to a shared bus and a shared memory by adding special registers for synchronization and communication between processors, aside from the shared memory. According to this technique, the processors determine whether they should execute the processes or stay busy-waiting, while repetitively reading the contents of the registers, so that synchronization among the processors are attained ("Stellix: UNIX for a Graphics Supercomputer", Proceedings of the Summer 1988 USENIX Conference, June 20-24, 1988, San Francisco Calif. USA, USENIX Association, pp. 321-330 Thomas J. Teixeira and Robert F. Gurwitz).
According to another approach, a register for synchronization is added to each register. These additional registers are connected through a bus used exclusively for synchronization. Each processor can determine the values in the registers exclusive for synchronization for other processors by snooping the bus exclusive for synchronization. In this approach, each processor also determines whether it should execute the processing or stay busy-waiting, while repetitively reading the contents of the registers, so that synchronization among the processors is attained. Each processor snoops and then updates its content, so that the frequency of access to the bus exclusive for synchronization may decrease However, the contents of the registers can not be changed at a high speed because of contention among signals on the bus exclusive for synchronization. In this approach, each processor also determines whether it should execute the processing or stay busy-waiting, while repetitively reading the content of the register, so that synchronization among processors is attained. ("VLSI Assist for a Multiprocessor", Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operation Systems, October 1987, pp. 10-20, Bob Beck, Bob Kasten and Shreekant Thakkar, 1987 ACM, pp. 10-20).
The above-described methods are effective in that they can reduce the frequency of using the shared bus and the shared memory, and can provide excellent system performance. However, they do not solve the problem of process serialization that leads to increase of overhead for synchronization because all processors must be busy-waiting for attaining synchronization and are forced to access the bus exclusive for synchronization while avoiding contention to this bus.
Another conventional solution to the problem of synchronization is described in Japanese Published Examined Patent Application No. 63-14387. According to the technique disclosed by this application, a synchronization controller is provided for each processor, and synchronization control lines are employed for communication of synchronization signals.
Japanese Published Unexamined Patent Application No. 59-24364 discloses a data flow type processing system in which token lines for receiving tokens (process termination signals) from each processor and firing signal lines for receiving firing signals to the processors are arranged in a matrix, and the intersection connecting states are set by flip-flops to permit dynamic change of intertask connections.